package day1_array.leetcode;

/**
 * @author yuisama
 * @date 2023年07月11日 11:42
 * @description 二维数组中的查找
 * 由于该数组中元素从左到右，从上至下依次非递减，所以从右上角开始寻找，若比查找元素小，向下；若比查找元素大，向左
 */
public class Offer_04_FindNumberIn2DArray {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        // 1.base case
        if (matrix.length == 0) {
            return false;
        }
        int i = 0,j = matrix[0].length - 1;
        // 此处不能写双重for循环，此处是单循环
        while (i < matrix.length && j >= 0) {
            if (target < matrix[i][j]) {
                // 向左走
                j --;
            }else if (target > matrix[i][j]) {
                // 向下走
                i ++;
            }else {
                return true;
            }
        }
        // 没找到
        return false;
    }
}
